package test5;

public class Demo4 {
    public static void main(String[] args) {
        System.out.println(minInsertions("(()))"));
    }

    public static int minInsertions(String s) {
        // need 记录需右括号的需求量
        int res = 0, need = 0;
        for (int i = 0; i < s.length(); i++) {
            // 一个左括号对应两个右括号
            if (s.charAt(i) == '(') {
                need += 2;
                if (need % 2 == 1) {
                    // 插入一个右括号
                    res++;
                    // 对右括号的需求减一，有现成的需求就 -1
                    need--;
                }
            }

            if (s.charAt(i) == ')') {
                need--;
                //右括号过多
                if (need == -1) {
                    // 插入一个左括号
                    res++;
                    need = 1;
                }
            }
        }
        return res + need;
    }
}
